/*
#Copyright (c) 2013, Philippe Bordron <philippe.bordron@gmail.com>
#
# This file is part of SIPPER.
#
# DCC is free software: you can redistribute it and/or modify
# it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# DCC is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU LESSER GENERAL PUBLIC LICENSE for more details.
#
# You should have received a copy of the GNU LESSER GENERAL PUBLIC LICENSE
# along with SIPPER.  If not, see <http://www.gnu.org/licenses/>
*/
package combi.wip.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import combi.wip.graph.PrefixTreeBinaryNode;

public class PrefixTreeYen<E> extends PrefixTreeBinaryNode<E> {

	private List<PrefixTreeBinaryNode<E>> selectedPaths; // ordered list by weight of selected path (the leaf of each path)
	private List<PrefixTreeBinaryNode<E>> candidatPaths; // ordered list by weight of candidat path (the leaf of each path)
	
	
	
	public PrefixTreeYen()
	{
		super(null, null, 1, new HashMap<PrefixTreeBinaryNode<E>, PrefixTreeBinaryNode<E>>());
		selectedPaths = new ArrayList<PrefixTreeBinaryNode<E>>();
		candidatPaths = new ArrayList<PrefixTreeBinaryNode<E>>();
	}
	

	/**
	 *  Get successors of the root
	 * @return
	 */
	public Collection<PrefixTreeNode<E>> getNodes()
	{
		return successors.values();
	}

	/**
	 * Add a sequence in the prefix tree
	 * @param seq
	 * @return the leaf node of seq.
	 */
	public PrefixTreeBinaryNode<E> addCandidat(List<E> seq)
	{
		PrefixTreeBinaryNode<E> result;
		ListIterator<E> it = seq.listIterator();
		candidatPaths.add((result = super.addSequence(it)));
		return result;
	}

	private List<PrefixTreeBinaryNode<E>> getCandidatPathsEnds()
	{
		return this.candidatPaths;
	}

	private List<PrefixTreeBinaryNode<E>> getSelectedPathsEnds()
	{
		return this.selectedPaths;
	}
	
	public List<List<E>> getAllCandidatPaths()
	{
		List<List<E>> result = new LinkedList<List<E>>();
		for (PrefixTreeNode<E> n : getCandidatPathsEnds())
		{
			result.add(n.getPrefix());
		}
		return result;
	}
	
	public List<List<E>> getAllSelectedPaths()
	{
		List<List<E>> result = new LinkedList<List<E>>();
		for (PrefixTreeNode<E> n : getSelectedPathsEnds())
		{
			result.add(n.getPrefix());
		}
		return result;
	}
	
	/**
	 * remove a sequence in the prefixe tree
	 * @param seq
	 * @return
	 */
	public void removeSequence(List<E> seq)
	{
		ListIterator<E> it = seq.listIterator();
		removeSequence(it);
	}

	/**
	 * Get the deviation node of the sequence seq in the prefix tree
	 * @param seq
	 * @return
	 */
	public PrefixTreeBinaryNode<E> getDeviationNode(List<E> seq)
	{
		return (PrefixTreeBinaryNode<E>) this.getDeviationNode(seq.listIterator());
	}


	/**
	 * Return a representation of the prefix tree in a String
	 */
	public String toString()
	{
		String res = "";
		for(PrefixTreeNode<E> n : successors.values())
		{
			res = res + n.toString(0);
		}
		return res;
	}

	/**
	 * Return the prefix tree into paths
	 */
	public List<List<E>> toPaths()
	{
		List<List<E>> result = new LinkedList<List<E>>();
		for (PrefixTreeNode<E> n : successors.values())
		{
			result.addAll(n.toPaths());
		}
		return result;
	}
	
	/**
	 * Get the root of the prefixe tree
	 * @return a PrefixNode
	 */
	public PrefixTreeBinaryNode<E> getRoot()
	{
		return this;
	}

	/**
	 * Test if the prefix tree is empty
	 * @return true if the prefix tree is empty (false else)
	 */
	public boolean isEmpty()
	{
		return successors.isEmpty();
	}
	
	/**
	 * Get the number of leafs in the prefix tree (i.e. the number of prefixes)
	 * @return the number of leafs
	 */
	public int getNumberOfCandidats()
	{
		return candidatPaths.size();
	}

	public int getNumberOfSelectedPaths()
	{
		return selectedPaths.size();
	}
	
	
	public void clear()
	{
		super.clear();
		this.devPoint.clear();
		this.setFirstSon(null);
		this.setLastSon(null);
		this.setNextBrother(null);
		this.setPreviousBrother(null);
	}

	
	/***
	 * push the best candidat path to the last selected path.
	 * 
	 */
	public void promoteBestCandidatPath()
	{
		selectedPaths.add(candidatPaths.remove(0));
	}
	
	public static void main(String[] args) {
		PrefixTreeYen<Integer> t = new PrefixTreeYen<Integer>();
		System.out.println(t);
		System.out.println("----------------");
		List<Integer> l;
		Integer[] l1 = new Integer[]{1,2,5,3,6};
		Integer[] l2 = new Integer[]{1,2,3,3,6};
		Integer[] l3 = new Integer[]{1,2,3,6,6};
		Integer[] l4 = new Integer[]{1,3,3,6,6};
		Integer[] l5 = new Integer[]{5,6,8,9,1,2};
		l = Arrays.asList(l1);
		PrefixTreeBinaryNode<Integer> end = t.addCandidat(l);
		System.out.println(end);
		System.out.println(t);
		System.out.println("----------------");
		l = Arrays.asList(l2);
		t.addCandidat(l);
		System.out.println(t);
		System.out.println("----------------");
		l = Arrays.asList(l3);
		t.addCandidat(l);
		System.out.println(t);
		System.out.println("----------------");
		l = Arrays.asList(l4);
		t.addCandidat(l);
		System.out.println(t);
		System.out.println("----------------");
		l = Arrays.asList(l5);
		t.addCandidat(l);
		System.out.println(t);
		System.out.println("----------------");
		t.removeSequence(l);
		System.out.println(t);
		System.out.println("----------------");

		Integer[] s = new Integer[]{1,4,3,6,6};
		l = Arrays.asList(s);
		System.out.println("----------------");
		System.out.println(t.getDeviationNode(l));
		System.out.println(t.getAllCandidatPaths());
		System.out.println(t.getAllSelectedPaths());
		System.out.println(t.toPaths());
		t.clear();

		System.out.println("----------------");
		System.out.println(t.toPaths());
	}
	
}
